home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1996 January / macformat-033.iso / mac / Shareware City / Developers / VideoToolbox / VideoToolboxSources / nrand.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-07-19  |  2.6 KB  |  70 lines  |  [TEXT/CWIE]
  1. /*
  2. nrand.c
  3. nrand(n) returns a random integer in the range [0, n-1], provided n>0. If n is zero
  4. the returned value is zero.
  5.  
  6. nrandU() and nrandUL() are obsolete; use nrand() instead.
  7.  
  8. NOTE:
  9. Frans Cornelissen showed me another way to implement nrand: rand()%n or
  10. randU()%n, instead of my n*rand()>>15 or n*randU()>>16. I used TimeCPU to
  11. compare the speeds; they're about the same:
  12.      22.362 µs    i=nrand(127);
  13.      19.684 µs    i=127L*randU()>>16;
  14.      18.226 µs    i=127L*rand()>>15;
  15.      20.891 µs    i=randU()%(unsigned short)127;
  16.      20.498 µs    i=rand()%127;
  17. This was on a PowerBook 170, compiled by CodeWarrior 5.5 using 4-byte ints.
  18. Note that the overhead of calling the nrand() subroutine (and its test of n),
  19. as opposed to evaluating the code inline, is only 3 µs out of 22 µs.
  20.  
  21. HISTORY:
  22. 4/29/88    dgp    wrote it.
  23. 3/19/90    dgp    made it portable between THINK C and MPW C.
  24. 9/13/92    dgp    Using THINK C's Disassembler I noticed that I could substantially speed
  25.             up the code, replacing the long division by a bit shift. The answers for 
  26.             legal values of n, i.e. n>0, are unchanged, but the answers for values of 
  27.             n outside that range have changed because I now explicitly cast n
  28.             to unsigned long rather than long. (Bit shifting and division give different
  29.             answers when the numerator is negative.)
  30.             Added nrandU() and nrandUL().
  31. 9/18/92    dgp    Cast rand() from int to unsigned short to prompt THINK C to generate 
  32.             tighter code.
  33. 3/26/94    dgp Replaced all three routines (nrand, nrandU, and nrandUL) by one universal
  34.             routine, nrand, that uses integer arithmetic (as in nrandU) if n is small 
  35.             enough, and otherwise uses double arithmetic (as in nrandUL). However,
  36.             even for small n, the new routine differs from the old nrandU() because
  37.             I replaced the call to rand() by a call to randU() because this
  38.             allows us to use integer arithmetic for values of n up to
  39.             USHRT_MAX instead of just SHRT_MAX.        
  40. */
  41. #include "VideoToolbox.h"
  42.  
  43. unsigned long nrand(unsigned long n)
  44. {
  45.     if(ULONG_MAX/USHRT_MAX/USHRT_MAX>=1 && n<=USHRT_MAX)return n*randU()>>16;
  46.     else return (unsigned long)((double)n*randUL()/(ULONG_MAX+1.0));
  47. }
  48.  
  49. #if 0    /* Old version, before March, 1994. */
  50.     int nrand(short n)
  51.     {
  52.         assert(RAND_MAX+1UL==1UL<<15);
  53.         return (unsigned long)n*rand()>>15;
  54.     }
  55.         
  56.     #if RAND_MAX > ULONG_MAX/USHRT_MAX
  57.         #error "nrandU() assumes that an unsigned long can hold the product of unsigned short & rand()."
  58.     #endif
  59.     
  60.     unsigned short nrandU(unsigned short n)
  61.     {
  62.         assert(RAND_MAX+1UL==1UL<<15);
  63.         return (unsigned long)n*(unsigned short)rand()>>15;
  64.     }
  65.  
  66.     unsigned long nrandUL(unsigned long n)
  67.     {
  68.         return (unsigned long)((double)n*randUL()/(ULONG_MAX+1.0)); 
  69.     }
  70. #endif